﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Solution5
{
    public string LongestPalindrome2(string s)
    {
        int maxLen = 0;
        int resstart = 0;

        for (int start = 0; start < s.Length; start++)
        {


            for (int end = start; end < s.Length; end++)
            {

                if (Palindrome(s, start, end))
                {
                    int curLen = end - start + 1;

                    if (curLen > maxLen)
                    {
                        maxLen = curLen;
                        resstart = start;
                    }

                }

            }
        }


        return s.Substring(resstart, maxLen);

    }

    private bool Palindrome(string s, int start, int end)
    {



        while (start < end)
        {//相等的时候必定是回文
            if (s[start] == s[end])
            {


                start++;
                end--;

            }
            else
            {
                return false;
            }
        }

        return true;

    }

    public string LongestPalindrome(string s)
    {

        //dp[start][end]= dp[start+1][end-1]//判断当前字母相同
        //两种情况，奇数，偶数

        int maxLen = 1;//没有回文的时候，返回第一个字母
        int resstart = 0;

        int len = s.Length;
        if (len <2)
        {
            return s;
        }

        bool[][] dp = new bool[s.Length][];
        for (int i = 0; i < len; i++)
        {

            dp[i] = new bool[len];

            dp[i][i] = true;//一个字母，原生就是回文

        }

        //先遍历所有的起点，再换长度
        //否则aaaa会拉掉，判断Start=0,end=3,dp[0][3]的时候，dp[1][2]还没有确定
        for (int curLen = 2; curLen <= len; curLen++)//先计算短的，才能转移长的
        {
            for (int start = 0; start < len; start++)//起点
        {
            
                int end = start + curLen - 1;

                if (end < len)
                {
                    if (s[start] == s[end])
                    {
                        if(curLen == 2)//长度为2，的话dp[start + 1][end - 1]没有这个状态，所以默认为0
                        {
                            dp[start][end] = true;
                        }
                        else
                        {
                            if (dp[start + 1][end - 1] )
                            {
                                dp[start][end] = true;
                            }
                        }

                      
                        

                    }
                    else
                    {
                        dp[start][end] = false;
                    }
               

                if (dp[start][end])
                {

                    if (curLen > maxLen)
                    {
                        maxLen = curLen;
                        resstart = start;
                    }

                }
                }

            }





        }
        return s.Substring(resstart, maxLen);


    }
}

class Progran5
{

    static void Main5(string[] args)
    {
        Solution5 solution = new Solution5();
        string s = "babad";
        string res = solution.LongestPalindrome(s);
        Console.WriteLine(res);
    }
}
